import javax.swing.tree.TreeNode;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * 判断是否为回文链表
     * @param head ListNode类 链表头
     * @return bool布尔型
     */
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    ListNode head;
    public boolean isPalindrome (ListNode head) {
        // write code here
        if (head == null) {
            return true;
        }

        ListNode cur = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }


        ListNode prev = null;
        while (slow != null) {
            ListNode curN = slow.next;
            slow.next = prev;
            prev = slow;
            slow = curN;
        }

        while (head != null) {
            if (head.val != prev.val) {
                return false;
            }
            head = head.next;
            prev = prev.next;
        }
        return true;
    }
}
//import java.util.HashSet;
//import java.util.Scanner;
//
//public class ceshi {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String str = scanner.nextLine();
//        scanner.close();
//        HashSet<Character> set = new HashSet<>();
//        for (int i = 0; i < str.length(); i++) {
//            set.add(str.charAt(i));
//        }
//
//        for (char c : set) {
//            System.out.print(c);
//        }
//    }
//}


